package main

import (
	"fmt"
	"strconv"
)

func main() {
	fmt.Printf("numDecodings(\"11106\"): %v\n", numDecodings("11106"))
}

// 数字解码
/*
1 对应A
2 对应B
3 对应C
...
*/
var memo map[int]int

func numDecodings(s string) int {
	memo = make(map[int]int, len(s))
	return f1(s, 0)
}

// 从s[i:]有多少种有效的方案
func f1(s string, i int) int {
	if i == len(s) {
		return 1
	}
	if _, ok := memo[i]; ok {
		return memo[i]
	}
	var ways int
	curN, _ := strconv.Atoi(string(s[i]))

	if curN == 0 {
		return 0
	}
	ways = f1(s, i+1)
	if i+1 < len(s) {
		nextN, _ := strconv.Atoi(string(s[i+1]))
		if curN*10+nextN <= 26 {
			ways += f1(s, i+2)
		}
	}
	memo[i] = ways
	return ways
}

func f2(s string) int {
	dp := make([]int, len(s)+1)
	dp[len(s)] = 1

	for i := len(s) - 1; i >= 0; i-- {
		curN, _ := strconv.Atoi(string(s[i]))
		if curN == 0 {
			dp[i] = 0
			continue
		}
		dp[i] = dp[i+1]
		if i+1 < len(s) {
			nextN, _ := strconv.Atoi(string(s[i+1]))
			if curN*10+nextN <= 26 {
				dp[i] += dp[i+2]
			}
		}
	}
	return dp[0]
}

func f3(s string) int {
	var a, b int
	a, b = 1, 0
	for i := len(s) - 1; i >= 0; i-- {
		cur := 0
		curN, _ := strconv.Atoi(string(s[i]))
		if curN == 0 {
			cur = 0
			b = a
			a = cur
			continue
		}
		cur = a
		if i+1 < len(s) {
			nextN, _ := strconv.Atoi(string(s[i+1]))
			if curN*10+nextN <= 26 {
				cur += b
			}
		}
		b = a
		a = cur
	}
	return a
}
